package com.hyb.algorithm.data.struct.queue;

/**
 *
 * 最大堆
 * @Author: huyanbing
 * @Date: 2021/9/2 7:45 下午
 */
public class MaxPQ<Key extends Comparable<Key>> {

    //存储元素的数组
    private Key[] pq;


    //当前Priority Queue 中的元素个数
    private int size;

    public MaxPQ(int n) {
        pq = (Key[]) new Comparable[n];
    }


    //返回当前队列中最大元素  0 不存 从1 开始
    public Key max() {
        return pq[1];
    }


    /**
     * 插入元素 e
     *
     * @param e
     */
    public void insert(Key e) {
        //容量加1
        size++;

        //将元素 e  放入 最后
        pq[size] = e;

        //上浮
        swim(size);

    }

    /**
     * 删除 并返回当前队列中最大元素
     *
     * @return
     */
    public Key delMax() {
        Key e = pq[1];
        //先将头节点 替换到 堆底
        swap(1, size);

        pq[size] = null;
        //减容量
        size--;

        sink(1);

        return e;
    }


    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    /**
     * 选择父节点
     *
     * @param k
     * @return
     */
    private int parent(int k) {
        return k / 2;
    }

    /**
     * 寻找左子树
     *
     * @param k
     * @return
     */
    private int leftChild(int k) {
        return k * 2;
    }

    /**
     * 寻找右子树
     *
     * @param k
     * @return
     */
    private int rightChild(int k) {
        return k * 2 + 1;
    }


    private void swap(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /**
     * 上浮
     */
    private void swim(int k) {
        // 如果浮到堆顶，就不能再上浮了
        while (k > 1 && less(parent(k), k)) {
            // 如果第 k 个元素⽐上层⼤  将 k 换上去
            swap(parent(k), k);
            k = parent(k);
        }
    }

    /**
     * 下沉
     */
    private void sink(int k) {

        //如果沉到堆底，就沉不下去了
        while (leftChild(k) <= size) {
            //先假设左边节点较大
            int older = leftChild(k);
            //如果右边节点存在  比一下大小
            if (rightChild(k) <= size && less(older, rightChild(k))) {
                older = rightChild(k);
            }

            //节点比两个孩子都大了 就不必下沉了
            if (less(older, k)) {
                break;
            }

            //否则 不符合最大堆的结构，下沉k 结点
            swap(k, older);

            k = older;
        }
    }


}


